package com.example.myapplication.Algorithm.ArrangeCoins;

///硬币的阶梯排列
///0
///00
///000
///0000
///00000
///000000
public class ArrangeCoins {
    public static void main(String[] args){
        System.out.println(arrangeCoins(16));
        System.out.println(arrangeCoins2(16));
        System.out.println(arrangeCoins3(16));
    }
    ///迭代
    public static int arrangeCoins(int n){
        //n在一边循环，一边减少（代表剩余数量）
        //i代表第几行，也代表该数量
        for(int i=1;i <=n;i++){
            n = n-i;
            //剩余数量少于该有数量时，返回行数
            if( n <= i ){
                return i;
            }
        }
        return  0;
    }

    ///二分查找
    public static int arrangeCoins2(int n){

        int low = 0;//从左向右走
        int high = n;//从右向左走
        int i = 0;
        while (low<=high){
            //低位小于高位
            int mid = ((high-low)/2)+low;//获取中间的i-第i行-该行有i个
            int cost = ((mid+1)*mid) / 2;//根据当前i，获取理所应当给的总数量
            if(cost == n){
                ///如果总数量外界给的实际数量相等，则返回i
                return mid;
            }else if(cost > n){
                high  = mid-1;
            }else{
                low  = mid+1;
            }
            i=mid;
        }
        return i-1;
    }

    ///牛顿迭代
    public static int arrangeCoins3(int n){
        if(n==0){
            return 0;
        }
        return (int)sqrt(n,n);
    }

    private static double sqrt(double x,int n){
        double res = (x+(2*n-x)/x)/2;
        if(res==x){
            return x;
        }else{
            return sqrt(res, n);
        }
    }

}
